#include <bits/stdc++.h>

using namespace std;

/**
    给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。
    你有2个机器人帮你收集樱桃，robots表示机器人的初始位置，
    机器人1 从 (robot[0][0], robot[0][1]) 出发，机器人2 从 (robot[1][0], robot[1][1]) 出发

    请你按照如下规则，返回两个机器人能收集的最多樱桃数目：

    从格子 (i,j) 出发，机器人1/2可以移动到周围的八个格子 即： (i-1, j+1)，(i, j+1)，(i+1, j+1)，(i-1, j-1)，(i, j-1)，(i+1, j-1)，(i+1, j)，(i-1, j)
    当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
    当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
    两个机器人在任意时刻都不能移动到 grid 外面。
    由于能量有限，机器人最多只能移动t步(t < rows x cols)
 */

class Solution
{
public:
    int cherryPickup(vector<vector<int>> &grid, vector<vector<int>> &robots, int t)
    {
        int rows = grid.size();
        if (rows == 0)
            return 0;
        int cols = grid[0].size();
        int x1 = robots[0][0], y1 = robots[0][1];
        int x2 = robots[1][0], y2 = robots[1][1];

        // Directions: 8 possible moves (excluding staying in place)
        vector<int> dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        vector<int> dy = {-1, 0, 1, -1, 1, -1, 0, 1};

        // DP table: dp[k][x1][y1][x2][y2]
        vector<vector<vector<vector<vector<int>>>>> dp(
            t + 1, vector<vector<vector<vector<int>>>>(
                       rows, vector<vector<vector<int>>>(
                                 cols, vector<vector<int>>(
                                           rows, vector<int>(cols, -1)))));

        // Initialize step 0
        int initial_cherry;
        if (x1 == x2 && y1 == y2)
        {
            initial_cherry = grid[x1][y1];
        }
        else
        {
            initial_cherry = grid[x1][y1] + grid[x2][y2];
        }
        dp[0][x1][y1][x2][y2] = initial_cherry;

        for (int k = 0; k < t; ++k)
        {
            for (int i1 = 0; i1 < rows; ++i1)
            {
                for (int j1 = 0; j1 < cols; ++j1)
                {
                    for (int i2 = 0; i2 < rows; ++i2)
                    {
                        for (int j2 = 0; j2 < cols; ++j2)
                        {
                            if (dp[k][i1][j1][i2][j2] == -1)
                                continue;

                            // Generate all possible moves for robot 1
                            for (int d1 = 0; d1 < 8; ++d1)
                            {
                                int ni1 = i1 + dx[d1];
                                int nj1 = j1 + dy[d1];
                                if (ni1 < 0 || ni1 >= rows || nj1 < 0 || nj1 >= cols)
                                    continue;

                                // Generate all possible moves for robot 2
                                for (int d2 = 0; d2 < 8; ++d2)
                                {
                                    int ni2 = i2 + dx[d2];
                                    int nj2 = j2 + dy[d2];
                                    if (ni2 < 0 || ni2 >= rows || nj2 < 0 || nj2 >= cols)
                                        continue;

                                    // Calculate cherries collected
                                    int cherries;
                                    if (ni1 == ni2 && nj1 == nj2)
                                    {
                                        cherries = grid[ni1][nj1];
                                    }
                                    else
                                    {
                                        cherries = grid[ni1][nj1] + grid[ni2][nj2];
                                    }

                                    // Update the DP state
                                    int total = dp[k][i1][j1][i2][j2] + cherries;
                                    if (total > dp[k + 1][ni1][nj1][ni2][nj2])
                                    {
                                        dp[k + 1][ni1][nj1][ni2][nj2] = total;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        // Find the maximum cherries collected over all steps and positions
        int max_cherry = 0;
        for (int k = 0; k <= t; ++k)
        {
            for (int i1 = 0; i1 < rows; ++i1)
            {
                for (int j1 = 0; j1 < cols; ++j1)
                {
                    for (int i2 = 0; i2 < rows; ++i2)
                    {
                        for (int j2 = 0; j2 < cols; ++j2)
                        {
                            max_cherry = max(max_cherry, dp[k][i1][j1][i2][j2]);
                        }
                    }
                }
            }
        }

        return max_cherry;
    }
};

int main(int argc, char const *argv[])
{
    vector<vector<int>> grid({{1, 0}, {0, 0}});
    int t = 4;
    vector<vector<int>> robots({{0, 0}, {1, 1}});
    cout << Solution().cherryPickup(grid, robots, t) << endl;
    return 0;
}
